package com.leetcode.题库;

/**
 * @author 覃国强
 * @date 2022-05-02 11:54
 */
public class 题库_0703_数据流中的第K大元素 {


  static
  class KthLargest {
    private final int[] arr;

    public KthLargest(int k, int[] nums) {
      this.arr = new int[k];
      for (int i = 0; i < k && i < nums.length; ++i) {
        arr[i] = nums[i];
      }
      if (nums.length < k) {
        for (int i = nums.length; i < k; ++i) {
          arr[i] = Integer.MIN_VALUE;
        }
      }
      init();
      for (int i = k; i < nums.length; ++i) {
        if (nums[i] > arr[0]) {
          arr[0] = nums[i];
          adjust(0);
        }
      }
    }

    private void adjust(int i) {
      if (i < arr.length) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        if (left < arr.length && right < arr.length) {
          if (arr[left] < arr[right]) {
            if (arr[i] > arr[left]) {
              swap(arr, i, left);
              adjust(left);
            }
          } else {
            if (arr[i] > arr[right]) {
              swap(arr, i , right);
              adjust(right);
            }
          }
        } else if (left < arr.length) {
          if (arr[i] > arr[left]) {
            swap(arr, i, left);
            adjust(left);
          }
        } else if (right < arr.length) {
          if (arr[i] > arr[right]) {
            swap(arr, i , right);
            adjust(right);
          }
        }
      }
    }

    private void init() {
      for (int i = (arr.length - 2) / 2; i >= 0; --i) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        if (left < arr.length && arr[i] > arr[left]) {
          swap(arr, i, left);
        }
        if (right < arr.length && arr[i] > arr[right]) {
          swap(arr, i, right);
        }
      }
    }

    private void swap(int[] arr, int i, int j) {
      int tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
    }

    public int add(int val) {
      if (val > arr[0]) {
        arr[0] = val;
        adjust(0);
      }
      return arr[0];
    }
  }

}
